# -*- coding: utf-8 -*-

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.min = 2147483647
        self.stack = []

    def push(self, x):
        """
        :type x: int
        :rtype: void
        """
        if x <= self.min:
            self.stack.append(self.min)
            self.min = x
        self.stack.append(x)
        print(self.stack)
        
    def pop(self):
        """
        :rtype: void
        """
        peak = self.stack.pop()
        if peak == self.min:
            self.min = self.stack.pop()

    def top(self):
        """
        :rtype: int
        """
        return self.stack[-1]

    def getMin(self):
        """
        :rtype: int
        """
        return self.min


# Your MinStack object will be instantiated and called as such:
obj = MinStack()
obj.push(3)
obj.push(1)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

# =============================================================================
# import random
# class Solution(object):
# 
#     def __init__(self, nums):
#         """
# 
#         :type nums: List[int]
#         :type size: int
#         """
#         self.origin = nums[:]
#         self.output = nums
# 
#     def reset(self):
#         """
#         Resets the array to its original configuration and return it.
#         :rtype: List[int]
#         """
#         return self.origin
# 
#     def shuffle(self):
#         """
#         Returns a random shuffling of the array.
#         :rtype: List[int]
#         """
#         n = len(self.output)
#         for i in range(n):
#             j = random.randint(0,n-1)   # 随机一个数字的位置和遍历的位置互换~,原来是i,n-1
#             self.output[i], self.output[j] = self.output[j], self.output[i]
#         return self.output
# =============================================================================

# Your Solution object will be instantiated and called as such:
# obj = Solution(nums)
# param_1 = obj.reset()
# param_2 = obj.shuffle()

# =============================================================================
# class Solution(object):
#     def rob(self, nums):
#         """
#         :type nums: List[int]
#         :rtype: int
#         """
#         if nums==[]:
#             return 0
#         if len(nums)==1:
#             return max(nums)
#         dp = [0]*len(nums)
#         dp[0] = nums[0]
#         dp[1] = max(nums[1],nums[0])
#         for i in range(2,len(nums)):
#             dp[i] = max(dp[i-1],dp[i-2]+nums[i])
# 
#         return dp[len(nums)-1]
# =============================================================================

# =============================================================================
# 
# class Solution:
#     def maxSubArray(self, nums):
#         """
#         :type nums: List[int]
#         :rtype: int
#         """
#         l = len(nums)
#         i = 0
#         sum = 0
#         MaxSum = nums[0]
#         while i < l:
#             sum+=nums[i]
#             if sum > MaxSum:
#                 MaxSum = sum
#             if sum < 0:
#                 sum = 0
#             i+=1
#         return MaxSum
# =============================================================================
# =============================================================================
# class Solution:
#     def maxProfit(self, prices):
#         """
#         :type prices: List[int]
#         :rtype: int
#         """
#         if len(prices)<2:
#             return 0
#         min_price = prices[0]
#         max_profile = 0
#         for i in prices:
#             min_price = min(min_price, i)
#             max_profile = max(max_profile, i - min_price) # 这个是当前值-前面的最小值
#         return max_profile
# =============================================================================

# =============================================================================
# # 原理:S(1)=1 S(2)=2,S(3)转换成假如我第一步走了一步,那么剩下的楼梯就是S(3-1)种走法
# # 假如我第一步走了二步,那么剩下的楼梯就是S(3-2)种走法
# # 则S(3)=S(1)+S(2)
# # 得出S(n)=S(n-1)+S(n-2)
# class Solution:
#     def climbStairs(self, n):
#         # write your code here
#         if n == 0: return 1
#         if n == 1: return 1
# 
#         tmpList = [1,1]
#         for i in range(0,n-1):
#             x = tmpList[-1] + tmpList[-2]
#             tmpList.append(x)
#         return tmpList[-1]
# =============================================================================
    

